#include <vector>
using namespace std;
class Solution {
public:

        //暴力枚举
        //时间复杂度：O(n^2)
        int int pivotIndex2(vector<int>& nums){
            int size=nums.size();
            for(int i = 0;i<size;i++)
            {
                int l = 0,r = i+1;
                int suml=0,sumr=0;
                while(l<i)
                {
                    suml+=nums[l++];
                }
                while(r<size)
                {
                    sumr+=nums[r++];
                }
                if(suml == sumr)
                    return i;
            }
            return -1;
        }


        //前缀和算法
        //时间复杂度：O(n)
    int pivotIndex2(vector<int>& nums) {
        int size = nums.size();
        //建立一个从原数组首部开始的前缀和数组（用于统计中心下标左侧的数据）
        vector<int> dp1(size); //vector会自动将各元素初始化为0
        //建立一个从原数组尾部开始的前缀和数组
        vector<int> dp2(size);

        for(int i = 1;i<size;++i)
        dp1[i]=dp1[i-1]+nums[i-1];

        for(int j = size-2;j>=0;--j)
        dp2[j]=dp2[j+1]+nums[j+1];

        for(int k = 0;k<size;++k) //如果存在多个中心下标因为是从左向右判断的当遇见一个中心下标直接返回就保证了先返回最左端的中心下标
        {
            if(dp1[k]==dp2[k])
            return k;
        }
        return -1;
    }
};